
/*
 * Question: Suppose that there is an additional field
 * 'parent' in a binary tree node which points to the
 * node's parent. Try to travel the binary tree in infix
 * order without stack.
 */

#include <iostream>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
public:
    bitree *parent;
};

void preprocess(bitree *rt)
{
    if(!rt) return;
    if (rt->lchild)
        rt->lchild->parent = rt;
    if (rt->rchild)
        rt->rchild->parent = rt;
    preprocess(rt->lchild);
    preprocess(rt->rchild);
}

void visit( bitree *rt )
{
    cout << rt->key << " ";
}

void inorder(bitree *rt)
{
    bitree *p;
    int tag;

    p = rt;
    tag = 0;
    while(p) {
        if(p->lchild && !tag) p = p->lchild;
        else {
            visit(p);
            if(p->rchild) {
                p = p->rchild;
                tag = 0;
            } else {
                while(p->parent && p->parent->rchild == p)
                    p = p->parent;
                p = p->parent;
                tag = 1;
            }
        }
    }
}

int main()
{
    bitree *rt;

    bitree_create<bitree,char>(rt, "ex40.txt");
    preprocess(rt);
    inorder(rt);
    cout << endl;
    bitree_destory(rt);

    return 0;
}

